package dp.multi;

import java.util.Arrays;

public class Solution_64 {

    /**
     * 二维 → 一维递推：把“只能向右/向下”的约束翻译成状态转移方程。
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] memo = new int[m][n];
        // 初始化成 -1 表示“未计算”，0 会和真正为 0 的格子混淆
        for (int[] row : memo) Arrays.fill(row, -1);
        return dfs(grid, m - 1, n - 1, memo);
    }

    private int dfs(int[][] grid, int i, int j, int[][] memo) {
        if (i < 0 || j < 0)
            //一定注意这里不是返回0，返回0就是可达了
            return Integer.MAX_VALUE;
        if (i == 0 && j == 0)
            return grid[0][0];
        if (memo[i][j] != -1)
            return memo[i][j];
        return memo[i][j] = Math.min(dfs(grid, i - 1, j, memo), dfs(grid, i, j - 1, memo)) + grid[i][j];
    }
}
